LeetCode 1. Two Sum

Thought

First Approach: Brute Force

Complecity: $O(n^2)$

Just use 2 for loops to iterate over the array and check if the sum is equal to the target.

Second Approach: Map

Complecity: $O(n)$

Use a map to store diff_between:index. If we find the diff in the map, we have found the pair.

Solution

C

int* twoSum(int* nums, int nums_size, int target, int* return_size) {
    int* result = (int*)malloc(sizeof(int) * 2);
    int i, j;
    for (i = 0; i < nums_size; i++) {
        for (j = i + 1; j < nums_size; j++) {
            if (nums[i] + nums[j] == target) {
                result[0] = i;
                result[1] = j;
                *return_size = 2;
                return result;
            }
        }
    }
    return result;
}

JAVASCRIPT

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
function twoSum(nums, target) {
    const m = new Map();
    for (const i in nums) {
        if (m.has(nums[i])) return [m.get(nums[i]), i];
        m.set(target - nums[i], i);
    }
}